package org.example.myleet.p995;

public class Solution {
    /**
     * 6 ms
     * 差分数组法
     *
     * 关键要想到用一个数组记录窗口内和窗口外翻转次数的差值，用于考察每个位置真正的翻转次数
     */
    public int minKBitFlips(int[] A, int K) {
        //flipCount是窗口内翻转的次数，count是翻转的总次数
        int n = A.length, flipCount = 0, count = 0;
        //diff是每个位置当其处于翻转窗口外的时候与窗口内的数位翻转的差值
        int[] diff = new int[n+1];
        for (int i=0; i<n; i++) {
            //当前窗口内位置的实际翻转次数
            flipCount += diff[i];
            if ((A[i] + flipCount) % 2 == 0) {
                //如果是偶数，说明当前位置是0，需要做翻转
                if (i + K > n) {
                    //但是如果后面位置不够K个，即不能翻转，但还是0，所以不能完成
                    return -1;
                }
                //总翻转+1
                ++count;
                //窗口内翻转+1
                ++flipCount;
                //窗口外翻转-1
                //注意当考察到窗口外i+K这个位置的时候其实会利用这个diff[i+K]与flipCount求和后重置为0
                //如果是窗口内i+K这个位置则会叠加已有的flipCount
                --diff[i+K];
            }
        }
        return count;
    }
}
